//https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-100-liked
//https://github.com/fuxuemingzhu/Leetcode-Solution-All/blob/main/100-199/198.%20House%20Robber%20%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.md

#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;


class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];

        std::vector<int> dp(nums.size(),0);
        dp[0]=nums[0];
        dp[1]=nums[1];

        for(int i=2;i<nums.size();++i){
            int tmp_max=0;
            for(int j=0;j<i-1;++j){
                tmp_max=std::max(tmp_max,dp[j]+nums[i]);
            }
            dp[i]=tmp_max;
        }
        //return *(max_element(dp.begin(),dp.end()));
        return std::max(dp[nums.size()-1],dp[nums.size()-2]);
    }
};